/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-26
 * Time: 20:39
 */

import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        Stack<TreeNode> stack=new Stack<>();
        TreeNode root=new TreeNode(preorder[0]);
        stack.push(root);
        //从左往右遍历,便利的同时链接上去
        for(int i=1;i<preorder.length;i++){
            TreeNode cur=new TreeNode(preorder[i]);
            TreeNode peek=stack.peek();
            TreeNode last=null;
            if(cur.val<peek.val){
                peek.left=cur;
                stack.push(cur);
            }else{
                while(peek.val<cur.val){
                    last=stack.pop();
                    if(stack.isEmpty()){
                        break;
                    }
                    peek=stack.peek();
                }
                //链接在最后一个出去的节点的右边,而不是栈顶节点的右边
                last.right=cur;
                stack.push(cur);
            }
        }
        return root;
    }
}
